package str

// 能做，但是超时了
func wordBreak(s string, wordDict []string) bool {

	var backtrack func(temp string, target string, wordDict []string) bool

	memory := make(map[string]bool)

	backtrack = func(temp, target string, wordDict []string) bool {

		if v, ok := memory[temp]; ok {
			return v
		}

		if len(temp) == len(target) && temp == target {
			memory[temp] = true
			return true
		} else if len(temp) > len(target) {
			return false
		}

		var res bool

		for _, s := range wordDict {
			res = backtrack(temp+s, target, wordDict)
			memory[temp+s] = res
			if res {
				return res
			}
		}
		return false
	}

	return backtrack("", s, wordDict)
}

// 可以且不超时
func wordBreak2(s string, wordDict []string) bool {

	if s == "" {
		return true
	}

	dp := make([]bool, len(s)+1)
	dp[0] = true
	for i := 1; i <= len(s); i++ {
		for _, v := range wordDict {
			wordLength := len(v)
			if i-wordLength >= 0 && dp[i-wordLength] && s[i-wordLength:i] == s {
				dp[i] = true
			}
		}
	}

	return dp[len(s)]

}
